package arithmetic.LeetCode;

/**
 * 排列组合
 * @author jiangfeng on 2022/6/28
 */
public class UniquePath {

    public static void main(String[] args) {
        // 463356416
        System.out.println(jie(18,9));
        System.out.println(463356416/362880);
        System.out.println(zuhe(25,10));
        //13 23  c // 548354040
        System.out.println(zuhe(8,2));
        //测试用例:36 7  41 6
        //				测试结果:4547031
        //				期望结果:4496388
        System.out.println(zuhe(41,6));
        // 2 100
        System.out.println(zuhe(100,99));
        //
        System.out.println(zuhe2(100,99));

        System.out.println(zuhe2(100,50));
        System.out.println(zuhe(100,50));
    }

    public static long jie(int n,int m){

        long res = 1;
        for (int i = 0; i < m; i++) {
            res*=(n--);
        }
        return res;
    }

    public static long zuhe(int n, int m) {
        // 优化
        if (m > n / 2) {
            m = n - m;
        }

        if (m == 1) {
            return n;
        }
        if (m == 2) {
            return (long) n * (n - 1) / 2;
        }
        if (n < 26) {


            long res = 1;
            for (int i = 0; i < m; i++) {
                res *= (n--);
                if(res<0){
                    throw new RuntimeException();
                }
            }
            long res1 = 1;
            for (int i = 1; i <= m; i++) {
                res1 *= i;
            }
            return res / res1;
        }

        return zuhe(n-1,m-1)+zuhe(n-1,m);
    }

    public static long zuhe2(int n, int m) {
        long res =1;
        m = Math.min(m,n-m);
        for(int i=1;i<=m;i++){
            res*=n+1-i;
            res/=i;
        }
        return res;
    }


}
